package com.ry.day1129;

public class LC193 {

    static class Solution {
        /**
         * @param s: a string
         * @return: return a integer
         */
        public int longestValidParentheses(String s) {
            //以i结尾的情况下，往左能扩出多长的有效区域 cache[0]=0
            int[] cache = new int[s.length()];

            int ans =0;
            int pre =0;
            for (int i = 1; i <s.length() ; i++) {
               if(s.charAt(i) ==')'){
                   pre = i-cache[i-1]-1;
                   if(pre >0 && s.charAt(pre) =='('){
                       cache[i] = cache[i-1]+2 +(pre>0 ? cache[pre-1]:0);
                   }
                   ans = Math.max(ans,cache[i]);
               }
            }
            return ans;
        }
    }

    public static void main(String[] args) {
        Solution obj = new Solution();
        System.out.println(obj.longestValidParentheses("(()"));
        System.out.println(obj.longestValidParentheses(")()())"));
    }
}


/*
LintCode-Logo
搜索题目、标签、题集
中文
您上个月的个人报告已生成，点击查看
avatar
193 · 最长有效括号
算法
中等
通过率
40%

题目
题解25
笔记
讨论90
排名
记录
描述
给出一个只包含'(' 和')'的字符串，找出其中最长的左右括号正确匹配的合法子串。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


样例
样例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
样例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"
相关知识
学习《2024年3月北美大厂最新面试真题精讲》课程中的4.3Mircosoft：最新面试精选002相关内容 ，了解更多相关知识！
标签
企业
Microsoft
相关题目

423
有效的括号序列
简单

427
生成括号
中等
推荐课程

系统设计 System Design 2024版
数据库、API、GFS、视频流等16大系统设计详解，实战练习拿下面试/晋升“拦路虎”
1496/1574
已开启智能提示
发起考试
30 分 00 秒
123456789

控制台
        历史提交

 */
